package org.lql.algo.codecrush.week003;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-07-30 15:36
 * @description: 876. 链表的中间结点 <a href="https://leetcode.cn/problems/middle-of-the-linked-list/description/">...</a>
 **/
public class MiddleNode {

    /**
     * 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
     * <p>
     * 如果有两个中间结点，则返回第二个中间结点。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5]
     * 输出：[3,4,5]
     * 解释：链表只有一个中间结点，值为 3 。
     * 示例 2：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5,6]
     * 输出：[4,5,6]
     * 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
     * <p>
     * <p>
     * 提示：
     * <p>
     * 链表的结点数范围是 [1, 100]
     * 1 <= Node.val <= 100
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        MiddleNode middleNode = new MiddleNode();
        ListNode listNode = middleNode.middleNode(head);
        printList(listNode);
    }

    private static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}


